package zwp.exercise.intereview.base.sort;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/28 15:29
 * @description 插入排序--优化后可升级为希尔排序(ShellSort) -- 都属于稳定排序
 */
public class InsertSort {
    public static void main(String[] args) {
        //定义数组,长度为8
        int[] array = {5, 9, 7, 4, 1, 3, 2, 8};
//                        j i
        for (int i = 1; i < array.length; i++) {
            //选择两个元素进行比较,初始值是两个挨着的索引
            int j = i - 1;
            //代表待插入元素
            int value = array[i];
            //如果待插入元素小于前面的值,
            //则继续和j-- (再前面的值进行比较)直到找到前面的值小于待插入元素索引,则该索引+1就是待插入值的索引
            //这样就把数组分为了有序和无序集合,i前面就是有序,>=i索引的就是无序集合
            while (j >= 0) {
                if (value < array[j]) {
                    array[j + 1] = array[j];
                    j--;
                } else {
                    break;
                }
            }
            array[j + 1] = value;
            System.out.println(Arrays.toString(array));
        }
    }
}
